package solution.design;

import java.util.HashMap;
import java.util.Random;

/**
 * @author zhangmin
 * @create 2021-10-28 15:40
 *
 * 710. 黑名单中的随机数
 * 给定一个包含 [0，n) 中不重复整数的黑名单 blacklist ，写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。
 * 可以将区间 [0,N) 看做一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时用一个哈希表进行映射：
 *
 * 1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。
 * 2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。
 * 3、数组中含有「空洞」（黑名单数字），也可以利用哈希表巧妙处理映射关系，让数组在逻辑上是紧凑的，方便随机取元素。
 */
public class RamdomWithBlacklist {

    int size;
    HashMap<Integer,Integer> map;
    Random random=new Random();

    // 构造函数，输入参数
    public RamdomWithBlacklist(int n, int[] blacklist) {
        size=n-blacklist.length;
        map=new HashMap<>();
        //最后一个元素的索引
        int lastInd=n-1;
        //需要确保需要映射到的最后的位置本身不在黑名单内
        for (int b:blacklist) {
            // 这里赋值多少都可以
            // 目的仅仅是把键存进哈希表
            // 方便快速判断数字是否在黑名单内
            map.put(b,0);
        }
        System.out.println(map);
        System.out.println("lastind="+lastInd);
        for (int i = 0; i < blacklist.length; i++) {
            System.out.println("b="+blacklist[i]);
            // 如果 b 已经在区间 [size, N)
            // 可以直接忽略
            if (blacklist[i]>=size){
                continue;
            }
            // 跳过所有黑名单中的数字
            while (map.containsKey(lastInd)) {
                lastInd--;
            }
            System.out.println("lastind--="+lastInd);
            //将黑名单中的元素映射到最后，将最后的元素映射到黑名单的元素的位置
            map.put(blacklist[i],lastInd);
            lastInd--;
            System.out.println("lastind="+lastInd);
            System.out.println(map);
        }
    }
    // 在区间 [0,N) 中等概率随机选取一个元素并返回
    // 这个元素不能是 blacklist 中的元素
    public int pick() {
        int index=random.nextInt(size);
        // 这个索引命中了黑名单，
        // 需要被映射到其他位置
        return map.getOrDefault(index,index);
    }

    public static void main(String[] args) {

        RamdomWithBlacklist obj=new RamdomWithBlacklist(7,new int[]{2,3,5});
        System.out.println(obj.pick());
        System.out.println(obj.pick());
        System.out.println(obj.pick());
        System.out.println(obj.pick());
        System.out.println(obj.pick());
        System.out.println(obj.pick());
        System.out.println(obj.pick());
    }
}
